package leetcode.周赛.第274场;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/2 13:16
 * @description：https://leetcode-cn.com/problems/maximum-employees-to-be-invited-to-a-meeting/
 */
public class 参加会议的最多员工数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.maximumInvitations(new int[]{1,0,0,2,1,4,7,8,9,6,7,10,8}));
    }

    class Solution {
        int[] favorite;

        public int maximumInvitations(int[] favorite) {
            if (favorite.length == 0) return 0;
            this.favorite = favorite;
            int max = 0;
            for (int i = 0; i < favorite.length; i++) {
                Map<Integer, int[]> table = new HashMap<>();
                max = Math.max(dfs(table, 0, i), max);
            }
            return max;
        }

        public int dfs(Map<Integer, int[]> table, int sum, int cur) {
            sum = dfs0(table, sum, cur);
            for (int i = 0; i < favorite.length; i++) {
                if (!table.containsKey(i))
                    sum = Math.max(sum, dfs0(table, sum, i));
            }
            return sum;
        }

        public int dfs0(Map<Integer, int[]> table, int sum, int cur) {
            int next = favorite[cur];
            int[] curSides = table.getOrDefault(cur, new int[]{-1, -1});
            int[] nextSides = table.getOrDefault(next, new int[]{-1, -1});
            if (nextSides[0] == cur || nextSides[1] == cur) return sum;
            if (curSides[0] != -1 && curSides[1] != -1) return sum;
            if (nextSides[0] != -1 && nextSides[1] != -1) return sum - 1;
            if (curSides[0] == -1) {
                curSides[0] = next;
            } else {
                curSides[1] = next;
            }
            if (nextSides[0] == -1) {
                nextSides[0] = cur;
            } else {
                nextSides[1] = cur;
            }
            if (!table.containsKey(cur)) sum++;
            if (!table.containsKey(next)) sum++;
            table.put(cur, curSides);
            table.put(next, nextSides);
            return dfs0(table, sum, next);
        }
    }
}
